#include "Sequence.h"
#include "Item.h"
#include "Log.h"
#include <list>
#include <vector>

template<class Container>
void partition_sequentially(Categorizer& cat,
                            typename Container::iterator begin,
                            int n,
                            std::vector<typename Container::iterator>& firsts,
                            std::vector<typename Container::iterator>& lasts,
                            std::vector<int>& ns) {
    LOG_ENTER(OBJECT,"Sequence::partition");

    // We'll do a bucket sort on the items, and will re-arrange the
    // list as we go.

    // First pass: get number of categories.
    typename Container::iterator iter = begin;
    int max_category = -1;
    for (int i = 0; i < n; i++) {
        int category = cat.get_category(**iter++);
        if (category > max_category)
            max_category = category;
    }

    // Second pass: get the sizes of all the categories.
    int *cat_sizes = new int[max_category + 1];
    for (int i = 0; i <= max_category; i++)
        cat_sizes[i] = 0;

    iter = begin;
    for (int i = 0; i < n; i++) {
        int category = cat.get_category(**iter++);
        cat_sizes[category]++;
    }

    int *cat_last = new int[max_category + 1];
    cat_last[0] = -1;
    for (int i = 1; i <= max_category; i++)
        cat_last[i] = cat_last[i-1] + cat_sizes[i-1];

    // Third pass: copy Item ptrs into big array, doing bucket sort
    Item **temp = new Item*[n];
    iter = begin;
    for (int i = 0; i < n; i++) {
        int category = cat.get_category(**iter++);
        temp[cat_last[category]++] = *iter;
    }

    // Fourth pass: copy sorted items back into linked list
    // As we go, create a sub-pile for each category
    iter = begin;
    firsts.clear();
    lasts.clear();
    int cat_start = -1;
    for (int i_cat = 0; i_cat <= max_category; i_cat++) {
        if (cat_sizes[i_cat] > 0) {
            typename Container::iterator first = iter;
            typename Container::iterator last;
            for (int i = cat_start; i < cat_start + cat_sizes[i_cat]; i++) {
                last = iter;
                *iter++ = temp[i];
            }
            firsts.push_back(first);
            lasts .push_back(last);
        }
    }
}

template
void partition_sequentially<std::list<Item*>>(
    Categorizer& cat,
    std::list<Item*>::iterator begin,
    int n,
    std::vector<std::list<Item*>::iterator>& firsts,
    std::vector<std::list<Item*>::iterator>& lasts,
    std::vector<int>& ns);
